/**
 * @version Create on 2012-10-29
 * @author Yinzi Chen
 */

public class BinaryTreeFromInorderAndPostorder {

	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public TreeNode buildTree(int[] inorder, int[] postorder) {
		int len = inorder.length;
		if (len == 0)
			return null;
		TreeNode root = new TreeNode(postorder[len - 1]);
		int i = 0;
		for (; i < len; ++i)
			if (inorder[i] == root.val)
				break;
		int lin[] = new int[i];
		int lpo[] = new int[i];
		for (int j = 0; j < i; ++j) {
			lin[j] = inorder[j];
			lpo[j] = postorder[j];
		}
		root.left = buildTree(lin, lpo);
		
		int rin[] = new int[len - 1 - i];
		int rpo[] = new int[len - 1 - i];
		for (int j = 0; j < len - 1 - i; ++j) {
			rin[j] = inorder[i + 1 + j];
			rpo[j] = postorder[i + j];
		}
		root.right = buildTree(rin, rpo);
		return root;
	}

	public static void main(String[] args) {
	}

}
